package person.bing.fbcloud.leetcode;

import java.util.*;
import java.util.stream.Collectors;

/**
 * @author: mengfanbing
 * @date: 2020/9/7 9:22
 */
public class Q347 {
    public static void main(String[] args) {
        int[] nums = {1,1,1,2,2,3};
        int k = 2;
        int[] ints = topKFrequent(nums, k);
        System.out.println(Arrays.toString(ints));
    }
    public static int[] topKFrequent(int[] nums, int k) {
        //使用map<ele,size>记录每种元素的出现次数
        //取出value，并排序，获得地第k个值kSize
        //遍历map获取value大于等于kSize的key
        int[] ans = new int[k];
        HashMap<Integer, Integer> eleSizeMap = new HashMap<>();
        for (int num:nums){
            if (Boolean.FALSE == eleSizeMap.containsKey(num)){
                eleSizeMap.put(num,1);
            }else {
                eleSizeMap.put(num,eleSizeMap.get(num)+1);
            }
        }
        Collection<Integer> values = eleSizeMap.values();
        Integer kSize = values.stream().sorted(Comparator.reverseOrder()).collect(Collectors.toList()).get(k - 1);
        int i=0;
        for (Map.Entry<Integer,Integer> entry:eleSizeMap.entrySet()){
            if (entry.getValue() >= kSize){
                ans[i++] = entry.getKey();
            }
        }
        return ans;
    }
}
